package com.datastructure;

public class LinkedListCRUD
{
    //头结点指针
    private LinkedNode head;
    //尾结点指针
    private LinkedNode last;
    //链表实际长度
    private int size;

//    /**
//     * 链表结点
//     */
//    private static class LinkedNode
//    {
//        int data;
//        LinkedNode next=null;
//        LinkedNode(int data)
//        {
//            this.data = data;
//        }
//    }

    /**
     * 链表查找元素
     *
     * @param index 查找的位置
     */
    public LinkedNode get(int index) throws Exception
    {
        if (index < 0 || index > size)
        {
            throw new IndexOutOfBoundsException("超出链表结点范围");
        }

        LinkedNode temp = head;
        for (int i = 0; i < index; i++)
        {
            temp = temp.next;
        }
        size--;
        return temp;
    }

    /**
     * 链表插入元素
     *
     * @param data  插入元素
     * @param index 插入位置
     */
    public void insert(int data, int index) throws Exception
    {
        if (index < 0 || index > size)
        {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }

        LinkedNode insertedNode = new LinkedNode(data);
        if (size == 0)
        {
            //空链表
            head = insertedNode;
            last = insertedNode;
        }
        else if (index == 0)
        {
            //插在头部
            insertedNode.next = head;
            head = insertedNode;
        }
        else if (size == index)
        {
            //插在尾部
            last.next = insertedNode;
            last = insertedNode;
        }
        else
        {
            //插在中间
            LinkedNode prevNode = get(index - 1);
            LinkedNode nextNode = prevNode.next;
            prevNode.next = insertedNode;
            insertedNode.next = nextNode;
        }
        size++;
    }

    /**
     * 链表删除位置
     *
     * @param index 删除的位置
     */
    public LinkedNode remove(int index) throws Exception
    {
        if (index < 0 || index > size)
        {
            throw new IndexOutOfBoundsException("超出链表范围");
        }

        LinkedNode removeNode = null;
        if (index == 0)
        {
            //删除头结点
            removeNode = head;
            head = head.next;
        }
        else if (index == size)
        {
            //删除尾结点
            LinkedNode prevNode = get(index - 1);
            removeNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;

        }
        else
        {
            //删除中间结点
            LinkedNode prevNode = get(index - 1);
            LinkedNode nextNode = prevNode.next.next;
            removeNode = prevNode.next;
            prevNode.next = nextNode;
        }
        return removeNode;
    }

    /**
     * 输出链表
     */
    public void output()
    {
        LinkedNode temp = head;
        while (temp != null)
        {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

}
